Section: New Results

Multiple Neighborhood Exploration Through Adaptive Search

Participants: Bilel Derbel, Houda Derbel, El-Ghazali Talbi, Hiba Yahyaoui

Variable neighborhood descent (VND) and its several variants are based on the systemic change of neighborhoods within the search. It is well known that the performance of a VND-like algorithm highly depends on the order/way the neighborhoods are alternated. In this work, we focus on designing new meta-strategies for deciding what neighborhood structure to apply through the search. Two new approaches are proposed to tackle this issue. In the first approach [41] , we model the search by considering the neighborhood tree induced by alternating the use of different structures within a local search descent. We investigate the issue of designing a search strategy operating at the neighborhood tree level by exploring different paths of the tree in a heuristic way. We show that allowing the search to 'backtrack' to a previously visited solution and resuming the iterative variable neighborhood descent by 'pruning' the already explored neighborhood branches leads to the design of effective and efficient search heuristics. In the second approach, we investigate deterministic and randomized adaptive strategies for selecting the next neighborhood to apply at runtime. The adaptive strategies are based on computing a reward for each neighborhood with respect to the observed average ratio of solution quality and time cost.